#include <stdio.h>
#include <stdlib.h>

#include "Common.h"

typedef struct String {
    char *value;
    int length;
    int (*index)(struct String *, struct String *, int);
} String;

int stringIndex(String *str1, String *str2, int pos);

void getNext(String *str, int *next);

int stringIndexKMP(String *str1, String *str2, int pos);

int main() {
    char str[] = "abcde";
    char *pStr = "abcde";
    int length = sizeof(str) / sizeof(char) - 1;
    int i;
    for (i = 0; i < length; i++) {
        int c = *(pStr + i);
        printf("%d\n", c);
    }

    printf("%s length=%d\n", str, length);
    char str1[] = "ababcababe";
    char str2[] = "ababe";
    String string1 = {str1, sizeof(str1) / sizeof(char) - 1};
    String string2 = {str2, sizeof(str2) / sizeof(char) - 1};
    int index = stringIndex(&string1, &string2, 0);

    String string3 = {"abacdababc", 10};
    int next[10];
    getNext(&string3, next);
    printf("index is %d\n", index);
    int index2 = stringIndexKMP(&string1, &string2, 0);
    printf("index2=%d\n", index2);
    return 0;
}

int stringIndexKMP(String *str1, String *str2, int pos) {
    int i = pos;
    int j = 0;
    int *const next = (int *)malloc(sizeof(int) * str2->length);
    getNext(str2, next);
    int count = 0;
    while (i < str1->length && j < str2->length) {
        if (j == -1 || str1->value[i] == str2->value[j]) {
            j++;
            i++;
        } else {
            j = next[j];
        }
        count++;
    }
    printf("KMP %d loops\n", count);
    if (j == str2->length) {
        return i - j;
    }
    return -1;
}

/*
比较难理解
*/
void getNext(String *str, int next[]) {
    int j = 0, k = -1;
    next[0] = -1;
    while (j < str->length - 1) {
        if (k == -1 || str->value[j] == str->value[k]) {
            if(str->value[++j] == str->value[++k]){
                next[j] = next[k];
            }else{
                next[j] = k;
            }
        } else {
            k = next[k];
        }
    }
}

int stringIndex(String *str1, String *str2, int pos) {
    int length1 = str1->length;
    int length2 = str2->length;
    if (pos > length1 - length2) {
        return -1;
    }
    int i = pos;
    int j = 0;
    int count = 0;
    while (i < length1 && j < length2) {
        if (*(str1->value + i) == *(str2->value + j)) {
            i++;
            j++;
        } else {
            i = i - j + 1;
            j = 0;
        }
        count++;
    }
    printf("%d loops\n", count);
    if (j == length2) {
        return i - j;
    }
    return -1;
}